/*
 * Created on Oct 17, 2005
 *
 * Copyright (c) 2005, the JUNG Project and the Regents of the University 
 * of California
 * All rights reserved.
 *
 * This software is open-source under the BSD license; see either
 * "license.txt" or
 * http://jung.sourceforge.net/license.txt for a description.
 */
package edu.uci.ics.jung.graph;

import java.util.Collection;

import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;

/**
 * A graph consisting of a set of vertices of type <code>V</code> set and a set
 * of edges of type <code>E</code>. Edges of this graph type have exactly two
 * endpoints; whether these endpoints must be distinct depends on the
 * implementation.
 * <P>
 * This interface permits, but does not enforce, any of the following common
 * variations of graphs:
 * <ul>
 * <li>directed and undirected edges
 * <li>vertices and edges with attributes (for example, weighted edges)
 * <li>vertices and edges of different types (for example, bipartite or
 * multimodal graphs)
 * <li>parallel edges (multiple edges which connect a single set of vertices)
 * <li>representations as matrices or as adjacency lists or adjacency maps
 * </ul>
 * Extensions or implementations of this interface may enforce or disallow any
 * or all of these variations.
 * 
 * <p>
 * Definitions (with respect to a given vertex <code>v</code>):
 * <ul>
 * <li><b>incoming edge</b> of <code>v</code>: an edge that can be traversed
 * from a neighbor of <code>v</code> to reach <code>v</code>
 * <li><b>outgoing edge</b> of <code>v</code>: an edge that can be traversed
 * from <code>v</code> to reach some neighbor of <code>v</code>
 * <li><b>predecessor</b> of <code>v</code>: a vertex at the other end of an
 * incoming edge of <code>v</code>
 * <li><b>successor</b> of <code>v</code>: a vertex at the other end of an
 * outgoing edge of <code>v</code>
 * </li>
 * </ul>
 * 
 * @author Joshua O'Madadhain
 */
public interface Graph<V, E> extends Hypergraph<V, E> {
	/**
	 * Returns a <code>Collection</code> view of the incoming edges incident to
	 * <code>vertex</code> in this graph.
	 * 
	 * @param vertex
	 *            the vertex whose incoming edges are to be returned
	 * @return a <code>Collection</code> view of the incoming edges incident to
	 *         <code>vertex</code> in this graph
	 */
	@Override
	Collection<E> getInEdges(V vertex);

	/**
	 * Returns a <code>Collection</code> view of the outgoing edges incident to
	 * <code>vertex</code> in this graph.
	 * 
	 * @param vertex
	 *            the vertex whose outgoing edges are to be returned
	 * @return a <code>Collection</code> view of the outgoing edges incident to
	 *         <code>vertex</code> in this graph
	 */
	@Override
	Collection<E> getOutEdges(V vertex);

	/**
	 * Returns a <code>Collection</code> view of the predecessors of
	 * <code>vertex</code> in this graph. A predecessor of <code>vertex</code>
	 * is defined as a vertex <code>v</code> which is connected to
	 * <code>vertex</code> by an edge <code>e</code>, where <code>e</code> is an
	 * outgoing edge of <code>v</code> and an incoming edge of
	 * <code>vertex</code>.
	 * 
	 * @param vertex
	 *            the vertex whose predecessors are to be returned
	 * @return a <code>Collection</code> view of the predecessors of
	 *         <code>vertex</code> in this graph
	 */
	@Override
	Collection<V> getPredecessors(V vertex);

	/**
	 * Returns a <code>Collection</code> view of the successors of
	 * <code>vertex</code> in this graph. A successor of <code>vertex</code> is
	 * defined as a vertex <code>v</code> which is connected to
	 * <code>vertex</code> by an edge <code>e</code>, where <code>e</code> is an
	 * incoming edge of <code>v</code> and an outgoing edge of
	 * <code>vertex</code>.
	 * 
	 * @param vertex
	 *            the vertex whose predecessors are to be returned
	 * @return a <code>Collection</code> view of the successors of
	 *         <code>vertex</code> in this graph
	 */
	@Override
	Collection<V> getSuccessors(V vertex);

	/**
	 * Returns the number of incoming edges incident to <code>vertex</code>.
	 * Equivalent to <code>getInEdges(vertex).size()</code>.
	 * 
	 * @param vertex
	 *            the vertex whose indegree is to be calculated
	 * @return the number of incoming edges incident to <code>vertex</code>
	 */
	@Override
	int inDegree(V vertex);

	/**
	 * Returns the number of outgoing edges incident to <code>vertex</code>.
	 * Equivalent to <code>getOutEdges(vertex).size()</code>.
	 * 
	 * @param vertex
	 *            the vertex whose outdegree is to be calculated
	 * @return the number of outgoing edges incident to <code>vertex</code>
	 */
	@Override
	int outDegree(V vertex);

	/**
	 * Returns <code>true</code> if <code>v1</code> is a predecessor of
	 * <code>v2</code> in this graph. Equivalent to
	 * <code>v1.getPredecessors().contains(v2)</code>.
	 * 
	 * @param v1
	 *            the first vertex to be queried
	 * @param v2
	 *            the second vertex to be queried
	 * @return <code>true</code> if <code>v1</code> is a predecessor of
	 *         <code>v2</code>, and false otherwise.
	 */
	boolean isPredecessor(V v1, V v2);

	/**
	 * Returns <code>true</code> if <code>v1</code> is a successor of
	 * <code>v2</code> in this graph. Equivalent to
	 * <code>v1.getSuccessors().contains(v2)</code>.
	 * 
	 * @param v1
	 *            the first vertex to be queried
	 * @param v2
	 *            the second vertex to be queried
	 * @return <code>true</code> if <code>v1</code> is a successor of
	 *         <code>v2</code>, and false otherwise.
	 */
	boolean isSuccessor(V v1, V v2);

	/**
	 * Returns the number of predecessors that <code>vertex</code> has in this
	 * graph. Equivalent to <code>vertex.getPredecessors().size()</code>.
	 * 
	 * @param vertex
	 *            the vertex whose predecessor count is to be returned
	 * @return the number of predecessors that <code>vertex</code> has in this
	 *         graph
	 */
	int getPredecessorCount(V vertex);

	/**
	 * Returns the number of successors that <code>vertex</code> has in this
	 * graph. Equivalent to <code>vertex.getSuccessors().size()</code>.
	 * 
	 * @param vertex
	 *            the vertex whose successor count is to be returned
	 * @return the number of successors that <code>vertex</code> has in this
	 *         graph
	 */
	int getSuccessorCount(V vertex);

	/**
	 * If <code>directed_edge</code> is a directed edge in this graph, returns
	 * the source; otherwise returns <code>null</code>. The source of a directed
	 * edge <code>d</code> is defined to be the vertex for which <code>d</code>
	 * is an outgoing edge. <code>directed_edge</code> is guaranteed to be a
	 * directed edge if its <code>EdgeType</code> is <code>DIRECTED</code>.
	 * 
	 * @param directed_edge
	 * @return the source of <code>directed_edge</code> if it is a directed edge
	 *         in this graph, or <code>null</code> otherwise
	 */
	@Override
	V getSource(E directed_edge);

	/**
	 * If <code>directed_edge</code> is a directed edge in this graph, returns
	 * the destination; otherwise returns <code>null</code>. The destination of
	 * a directed edge <code>d</code> is defined to be the vertex incident to
	 * <code>d</code> for which <code>d</code> is an incoming edge.
	 * <code>directed_edge</code> is guaranteed to be a directed edge if its
	 * <code>EdgeType</code> is <code>DIRECTED</code>.
	 * 
	 * @param directed_edge
	 * @return the destination of <code>directed_edge</code> if it is a directed
	 *         edge in this graph, or <code>null</code> otherwise
	 */
	@Override
	V getDest(E directed_edge);

	/**
	 * Returns <code>true</code> if <code>vertex</code> is the source of
	 * <code>edge</code>. Equivalent to
	 * <code>getSource(edge).equals(vertex)</code>.
	 * 
	 * @param vertex
	 *            the vertex to be queried
	 * @param edge
	 *            the edge to be queried
	 * @return <code>true</code> iff <code>vertex</code> is the source of
	 *         <code>edge</code>
	 */
	boolean isSource(V vertex, E edge);

	/**
	 * Returns <code>true</code> if <code>vertex</code> is the destination of
	 * <code>edge</code>. Equivalent to
	 * <code>getDest(edge).equals(vertex)</code>.
	 * 
	 * @param vertex
	 *            the vertex to be queried
	 * @param edge
	 *            the edge to be queried
	 * @return <code>true</code> iff <code>vertex</code> is the destination of
	 *         <code>edge</code>
	 */
	boolean isDest(V vertex, E edge);

	/**
	 * Adds edge <code>e</code> to this graph such that it connects vertex
	 * <code>v1</code> to <code>v2</code>. Equivalent to
	 * <code>addEdge(e, new Pair&lt;V&gt;(v1, v2))</code>. If this graph does not
	 * contain <code>v1</code>, <code>v2</code>, or both, implementations may
	 * choose to either silently add the vertices to the graph or throw an
	 * <code>IllegalArgumentException</code>. If this graph assigns edge types
	 * to its edges, the edge type of <code>e</code> will be the default for
	 * this graph. See <code>Hypergraph.addEdge()</code> for a listing of
	 * possible reasons for failure.
	 * 
	 * @param e
	 *            the edge to be added
	 * @param v1
	 *            the first vertex to be connected
	 * @param v2
	 *            the second vertex to be connected
	 * @return <code>true</code> if the add is successful, <code>false</code>
	 *         otherwise
	 * @see Hypergraph#addEdge(Object, Collection)
	 * @see #addEdge(Object, Object, Object, EdgeType)
	 */
	boolean addEdge(E e, V v1, V v2);

	/**
	 * Adds edge <code>e</code> to this graph such that it connects vertex
	 * <code>v1</code> to <code>v2</code>. Equivalent to
	 * <code>addEdge(e, new Pair&lt;V&gt;(v1, v2))</code>. If this graph does not
	 * contain <code>v1</code>, <code>v2</code>, or both, implementations may
	 * choose to either silently add the vertices to the graph or throw an
	 * <code>IllegalArgumentException</code>. If <code>edgeType</code> is not
	 * legal for this graph, this method will throw
	 * <code>IllegalArgumentException</code>. See
	 * <code>Hypergraph.addEdge()</code> for a listing of possible reasons for
	 * failure.
	 * 
	 * @param e
	 *            the edge to be added
	 * @param v1
	 *            the first vertex to be connected
	 * @param v2
	 *            the second vertex to be connected
	 * @param edgeType
	 *            the type to be assigned to the edge
	 * @return <code>true</code> if the add is successful, <code>false</code>
	 *         otherwise
	 * @see Hypergraph#addEdge(Object, Collection)
	 * @see #addEdge(Object, Object, Object)
	 */
	boolean addEdge(E e, V v1, V v2, EdgeType edgeType);

	/**
	 * Returns the endpoints of <code>edge</code> as a <code>Pair&lt;V&gt;</code>.
	 * 
	 * @param edge
	 *            the edge whose endpoints are to be returned
	 * @return the endpoints (incident vertices) of <code>edge</code>
	 */
	Pair<V> getEndpoints(E edge);

	/**
	 * Returns the vertex at the other end of <code>edge</code> from
	 * <code>vertex</code>. (That is, returns the vertex incident to
	 * <code>edge</code> which is not <code>vertex</code>.)
	 * 
	 * @param vertex
	 *            the vertex to be queried
	 * @param edge
	 *            the edge to be queried
	 * @return the vertex at the other end of <code>edge</code> from
	 *         <code>vertex</code>
	 */
	V getOpposite(V vertex, E edge);

	@Override
	Graph<V, E> newInstance();
}
